1. Field of the Invention
The present invention relates to a method of incremental statistical static timing analysis (SSTA) of a very-large-scale-integration (VLSI) circuit, and more particularly, to a method of incremental SSTA based on a probability statistics method, for effective timing analysis through incremental analysis in the case of optimizing a timing yield and for predicting a timing yield more accurately.
2. Description of the Related Art
In the fabrication of very-large-scale-integration (VLSI) circuits, variations in chip performance become more significant due to variations in the manufacturing process, which increase as fabrication techniques become more intricate, and thus a loss in chip yield becomes a serious problem. To resolve this problem, it is necessary not only to improve fabrication techniques, but also to analyze effects of variations in the manufacturing process with respect to chip performance and consider the effects when a chip is being designed.
As a major analyzing method to analyze effects of variations in the manufacturing process with respect to chip performance, statistical static timing analysis (SSTA) has been suggested. According to the SSTA, timings of a chip are indicated as a probability distribution, and a timing yield, which is a probability that a chip satisfies given timing constraints, is predicted based on the distribution of probabilities.
Analysis of a circuit is repeatedly performed when the circuit is designed and when the circuit is optimized. Thus, it is not efficient to repeat such analysis every time when one or more subtle changes occur in a circuit. A method of incremental analysis, which is suggested as a method for efficient design and optimization of a circuit, is a method that updates results corresponding to only changed portions of a circuit based on previous analysis results when there are subtle changes in the circuit.
Regarding SSTA, a method of tightness probability based incremental analysis (TBIA) using tightness probability, which is a probability that a particular probability variable is greater than other probability variables, is suggested in Reference 1.    [Reference 1] C. Visweswariah, K. Ravindran, K. Kalafala, S. G. Walker, S. Narayan, D. K. Beece, J. Piaget, N. Venkateswaran, and J. G. Hemmett, “First-order incremental block-based statistical timing analysis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 10, pp. 2170-2180, October 2006.
FIG. 1 is a diagram showing a digital circuit having gates to describe timing analysis, and FIG. 2 is a timing graph with respect to the circuit of FIG. 1.
Timing analysis of a circuit is performed using a timing graph, and primary inputs and primary outputs of the circuit are connected to one virtual source node 100 and one virtual sink node 110, respectively. Thus, the virtual source node 100 is the starting point of all circuit signals, whereas the virtual sink node 110 is the destination point of all circuit signals.
Furthermore, input pins and output pins of the gates are replaced with nodes that correspond to each respective pin. Signal paths from the input pins to the output pins of the gates are connected by edges, and a weight of an edge indicates a delay of a corresponding path. Interconnection between the gates and delays of the interconnection are also replaced with an edge and an edge weight. Numbers 1 through 10 of the input pins and output pins in FIG. 1 correspond to nodes 1 through 10 in FIG. 2, and primary inputs and primary outputs are connected to a virtual source node and a virtual sink node, respectively.
According to static timing analysis, an arrival time at each node is determined by the maximum value of arrival times of all fanin edges in MAX operation. Here, the arrival time is a time period for transmitting a signal from a virtual source node to a node, and an arrival time of an edge can be calculated by adding a delay of the edge to an arrival time of an input node in ADD operation. The arrival time of a node is transmitted to a next node via an output edge, wherein the transmission process is referred as delay propagation.
A required arrival time of a node is a latest arrival time of the node to avoid timing failure, and can be calculated by performing delay propagation backward, that is, from a virtual sink node to a virtual source node, according to timing constraints of a circuit.
According to deterministic static timing analysis, when a gate is replaced, delay is propagated from the replaced gate to a sink node. In a timing graph, arrival time is updated from an edge having a changed edge delay with respect to fanout nodes. Here, even if delays of a part of fanin edges at an arbitrary node is changed, if arrival time of the node is not changed when maximum value the delays is computed, updating arrival times with respect to fanouts of the node may be omitted.
According to statistical static timing analysis, a change in an arrival time of an arbitrary node affects arrival times of all fanout nodes. Thus, for errorless performance of incremental analysis, it is necessary to update arrival times of all fanout gates of a replaced gate. However, it is very inefficient to update a large number of arrival times in this case. Thus, for efficient analysis, if a change of arrival time at the arbitrary node is not significant, delay propagation to fanout gates may be partially omitted regardless of the occurrence of some errors.
According to tightness probability based incremental analysis, when a tightness probability of a changed input delay of a gate is less than a particular threshold value before and after gate replacement, delay propagation from the corresponding gate is stopped, so that efficiency with respect to delay propagation is improved. However, since a timing yield is not directly considered, the timing yield cannot be accurately predicted.